import Util.ListNode;

/**
 * 双指针判断链表中有没有环，有环则返回环的入口。
 */
public class Solution23 {

    public ListNode detectCycle(ListNode head){
        ListNode fast = head, slow = head;
        while (true){
            if (fast == null || fast.next == null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                break;
        }
        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
